The invention relates to a frequency-domain block-adaptive digital filter having a finite impulse response of length N for filtering a time-domain input signal in accordance with the overlap-save method.
A frequency-domain adaptive filter (FDAF) having such a structure is disclosed in the article "A Unified Approach to Time- and Frequency-Domain Realization of FIR Adaptive Digital Filters" by G. A. Clark et al. in IEEE Trans. Acoust., Speech, Signal Processing, Vol. ASSP-31, No. 5, October 1983, pages 1073-1083, more specifically FIG. 2.
In the field of speech and data transmission, time-domain adaptive filters (TDAF) are used in the majority of cases and in most practical applications these TDAF's are implemented as adaptive transversal filters, in which a "least-mean-square" (LMS) algorithm is used for adapting the weights. When the length N of the impulse response assumes large values, as is the case with applications in the acoustic field, the TDAF implemented as a transversal filter has the disadvantage that the complexity in terms of arithmetic operations (multiplying and adding) per output sample increases linearly with the filter length N. In addition, the TDAF implemented as a transversal filter has a low convergence rate for highly correlated input signals such as speech and certain types of data, since the convergence rate decreases with an increasing ratio of the maximum to minimum eigenvalues of the correlation matrix of the input signal (see, for example, C. W. K. Gritton and D. W. Lin, "Echo Cancellation Algorithms", IEEE ASSP Magazine, April 1984, pp. 30-38, in particular pp. 32/33).
The use of frequency-domain adaptive filters (FDAF) provides the possibility to significantly improve the convergence properties for highly correlated input signals, as for any of the substantially orthogonal frequency-domain components of the input signal the gain factor in the adaptation-algorithm can be normalized in a simple way in accordance with the power of the relevant frequency component. For the most efficient implementation of a FDAF having an impulse response of length N, use is made of Discrete Fourier Transforms (DFT) of length 2N of 2N weighting factors to ensure that circular convolutions and correlations, computed with the aid of DFT's, are equivalent to the desired linear convolutions and correlations when the sectioning method is performed correctly. For large values N the computational complexity can, however, be significantly reduced in terms of arithmetic operations per output sample by utilizing efficient implementations of the DFT known as "Fast Fourier Transform" (FFT), as a result of which this complexity becomes proportional to the logarithm of the filter length N.
There where a TDAF needs only have N weighting factors for an impulse response of length N, the equivalent FDAF must utilize 2N weighting factors. After convergence, the weighting factors of an adaptive digital filter (TDAF and FDAF) will continue to fluctuate around their final values due to the presence of noise or other types of signals superimposed on the reference signal and because of the precision (that is to say word length or number of bits) with which the different signals in the digital filter are represented. With the customary, practically valid assumptions about the statistic independence of the different quantities in the filter, the weighting factors will have the same variances when no use is made of window functions in the adaptation loop of the filter. This implies that at the same convergence rate of the adaptive filter (that is to say the same gain factor in the adaption algorithm) using 2N instead of N weighting factors results in an increase of the final misalignment noise factor of the filter by 3 dB, since the final misalignment noise factor is determined by the sum of the variances of the weighting factors. In practice, the gain factor in the adaptation algorithm is chosen such that a predetermined value of the final misalignment noise factor is not exceeded. In order to compensate for the increase of the final misalignment noise factor in an FDAF, this gain factor must be halved, which causes the convergence rate also to be halved, whereas in the majority of applications a highest possible convergence rate is pursued.
Said article by Clark et al. describes a solution for this problem with reference to FIGS. 2 and 3, the modifications of the 2N frequency-domain weighting factors not being derived directly from the second multiplier means, but by using window means for performing an operation whose time-domain equivalent is a multiplication by a rectangular window function of length 2N which constrains the last N components to be zero. An implementation of this window function in the time-domain requires the use of 2 DFT's, namely an inverse DFT for the transformation to the time-domain and a DFT to effect the transformation to the frequency-domain after multiplication by the time-domain window function. An alternative implementation is based on the consideration that a multiplication in the time-domain is equivalent to a convolution in the frequency-domain with the components of the DFT of length 2N of this time-domain window function. For high values N this alternative implementation in the frequency-domain is not attractive, as its computational complexity per component increases linearly with N, whereas in the first-mentioned time-domain implementation this complexity becomes proportional to the logarithm of N when the 2 DFT' s are implemented as FFT's. Thus, a preferred implementation of the known solution results in an FDAF containing a total of 5 DFT's implemented as FFT's.